package com.LeeCode;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 蛇梯棋
 */

public class Code909 {
    public static void main(String[] args) {
        int[][] matrix = {
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, 35, -1, -1, 13, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, 15, -1, -1, -1, -1}
        };
        System.out.println(new Code909().snakesAndLadders(matrix));
    }

    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        boolean[] visited = new boolean[n * n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        visited[1] = true;

        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();

                // 如果到达终点
                if (cur == n * n) {
                    return steps;
                }

                // 掷骰子 1~6
                for (int j = 1; j <= 6; j++) {
                    int next = cur + j;
                    if (next > n * n) continue;

                    int[] pos = num2Index(next, n);
                    int x = pos[0], y = pos[1];

                    // 如果有蛇或梯子，跳转
                    if (board[x][y] != -1) {
                        next = board[x][y];
                    }

                    if (!visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
            steps++;
        }

        return -1; // 无法到达终点
    }

    private int[] num2Index(int num, int n) {
        int[] res = new int[2];
        num--; // 转为 0-based index
        int x = num / n, y = num % n;
        res[0] = n - 1 - x;
        if (x % 2 == 0) {
            res[1] = y;
        } else {
            res[1] = n - 1 - y;
        }
        return res;
    }
}
